package com.linwen.excise.leetcode;

import java.util.Arrays;

/**
 * @ClassName _1502判断能否形成等差数列
 * @Description TODO
 * @Author zero
 * @DATE 2024/9/28 5:28 PM
 * @Version 1.0
 */
public class _1502判断能否形成等差数列 {
    public static void main(String[] args) {
        _1502判断能否形成等差数列 inst = new _1502判断能否形成等差数列();
        int[] arr = {3,5,1};
        System.out.println(inst.canMakeArithmeticProgression(arr));
        System.out.println(inst.canMakeArithmeticProgression2(arr));
    }

    public boolean canMakeArithmeticProgression2(int[] arr) {
        // 1. 先遍历第一遍，得出最大值和最小值。
        int max = arr[0];
        int min = arr[0];
        for(int a: arr) {
            if(a > max) {
                max = a;
            }
            else if(a < min) {
                min = a;
            }
        }
        // 2. 如果最大值最小值相等，则肯定是等差数列。
        if(max == min) {
            return true;
        }
        // 3. 否则（最大值大于最小值）最大值和最小值的差记为diff。
        int diff = max - min;
        //   3.1 如果diff不能被nums.length - 1整除，不是等差数列。
        if(diff % (arr.length - 1) != 0) {
            return false;
        }
        //   3.2 如果能整除，商x就是公差。
        int x = diff / (arr.length - 1);
        boolean[] hasOccured = new boolean[arr.length];
        for(int i = 0; i < arr.length; i++) {
            //     3.2.1 再遍历第二遍，看每个数减去最小值能不能被x整除，不能的话，不是等差数列。
            if((arr[i] - min) % x != 0) {
                return false;
            }
            //     3.2.2 能整除的话，商可以表示这个元素是等差数列的第几个元素。用一个临时数组（长度也是nums.length）标记一下这第几个元素是否出现过，如果出现过就有重复值，不是等差数列。
            int position = (arr[i] - min) / x;
            if(hasOccured[position]) {
                return false;
            }
            hasOccured[position] = true;
        }
        //     3.2.3 如果每个元素都是唯一的，则是等差数列。
        return true;
    }

    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int temp = arr[1] - arr[0];
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != temp) {
                return false;
            }
        }
        return true;
    }
}
